Fast fourier hardware implementation

in this blog, I am trying to explain how to construct a Fast fourier transform into a hardware. lets first see the formula of FFT.

from this formula, where the ouput is X[k] and the data input x[n], since

we can construct the Wn (twiddle factor) into a constants. so the output of fft wouldbe X[k]= x[n]*constant. when it comes to a constant, in the hardware we can make a look up table or a library which consist this constants. We need to carefull when calculate the FFT, it has real value and imaginary value. so the twiddle factor would be consist of two part, those are the real one and imaginary one.

the derivation of first formula shown on figure below:

from the derivation, we need to split the resul into two parts, even and odd. and construct the radix-2 cooley-tukey

this is the example of 8 points radix-2 FFT, and for 32 points radix-2 FFT shown in figure below:

we need to see that the left side, how to arrange the data input. The arrage comes from reverse byte.

and then we need to simulate it into model sim and compare the result with matlab.

output imaginer

model_output imaginer

output real:

model_output real:

this is the simulation result of FFT32 point in model-sim, the data type is fixed-point.